DESCRIPTION: It has been demonstrated in animal models that when tumor cells transduced with cytokine genes are administered to syngeneic hosts, the relevant cytokine is produced at the injection site and the acquisition of tumor protective immunity is enhanced. Application in men is encumbered by the need to harvest autologous tumor, successfully transduce the cells and generate adequate cell numbers for a vaccine. The investigator's approach circumvents these problems by using recombinant vaccinia virus to insert the relevant genes into tumor cells in vivo (in situ). Vaccinia is used for gene transfer because of its large capacity and efficiency in delivering passenger genes into the cytoplasm of infected cells. In the weakly immunogenic B16 murine melanoma model, GM-CSF transduced tumor cells are superior in inducing protective immunity. The investigator's will focus on metastatic melanoma because intralesional wild-type vaccinia alone induced regression of about 20 percent of injected lesions. The objectives of this Phase I/II trial of intralesional immunotherapy with a vaccinia/GM-CSF recombinant virus in patients with metastatic melanoma are: Phase I Determine the highest dose (from among those tested) which can be safely (Grade 0, 1 or 2 toxicity) and effectively (sustain GM-CSF production) administered twice weekly for five weeks. Demonstrate viral infection of tumor cells and viral GM-CSF production (mRNA by RT-PCR) and lymphocyte infiltration, (immunohistochemistry) at injection sites and serum GM-CSF levels (ELISA). Measure anti- vaccinia antibody (ELISA) for qualitative correlation with viral infection and cytokine gene function. Phase II Repeat Phase I in vivo and in vitro studies. Measure the resultant anti-tumor immunity: DTH, lymphocyte proliferation, CTL (chromium release, cytokine production). Observe for objective tumor regression in injected and uninjected metastases.